/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-06-24
 * Time: 9:45
 */
class Solution16 {
    boolean[][] row,col;
    boolean[][][] grid;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];

        //初始化
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                }
            }
        }
        dfs(board);
    }

    boolean dfs(char[][] board){
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') {
                    //填数
                    for(int num = 1; num <= 9;num++) {
                        //剪枝
                        if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]) {
                            board[i][j] = (char)('0'+num);
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                            //告诉这个位置填的正确
                            //填好这个位置，去下一个位置
                            if(dfs(board) == true) {
                                //!!
                                return true;
                            }
                            //如果判断不成立，num++，尝试下一个数，需要恢复现场
                            //恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;
                        }
                    }
                    //!!这个数从1-9遍历了没填，告诉没有填的，填哪一个都不行
                    //此时重新选,上面那个选错了
                    return false;
                }
            }
        }
        //两层for循环 把表格填好了
        return true;
    }
}
